// 单链表运算算法
#include <stdio.h>
#include <mm_malloc.h> // window上 #include <malloc.h>

// 单链表结点类型
struct ListNode
{
	// 存放结点值
	int val;	
	
	// 存放后继结点的地址
	ListNode *next;
	
	// 构造函数
	ListNode() : val(0), next(NULL) {} // 默认构造函数
	ListNode(int x) : val(x), next(NULL) {}	// 重载构造函数1
	ListNode(int x, ListNode *next):val(x), next(next) {} // 重载构造函数2
};

// 头插法建立单链表
void CreateListF(ListNode *&L,int a[],int n)
{
	// 辅助指针
	ListNode *s;
	
	// 创建头结点
	L = (ListNode *)malloc(sizeof(ListNode));
	L->next = NULL;
	
	// 添加结点
	for (int i=0; i<n; i++)
	{
		// 创建新结点s
		s=(ListNode *)malloc(sizeof(ListNode));
		s->val=a[i];
		
		// 将结点s插在原开始结点之前,头结点之后
		s->next=L->next;
		L->next=s;
	}
}

// 尾插法建立单链表
void CreateListR(ListNode *&L, int a[], int n)
{
	ListNode *s, *r;
	
	// 创建头结点
	L = (ListNode *)malloc(sizeof(ListNode));
	L->next=NULL;
	
	// r始终指向尾结点,开始时指向头结点
	r = L;
	
	
	for (int i=0; i<n; i++)
	{
		// 创建新结点s
		s=(ListNode *)malloc(sizeof(ListNode));
		s->val=a[i];
		
		// 将结点s插入r结点之后
		r->next=s;
		r=s;
	}
	
	// 尾结点next域置为NULL
	r->next=NULL;
}

// 初始化线性表
void InitList(ListNode *&L)
{
	// 创建头结点
	L=(ListNode *)malloc(sizeof(ListNode));
	
	// 单链表置为空表
	L->next=NULL;
}

// 销毁线性表
void DestroyList(ListNode *&L)
{
	ListNode *pre=L, *p=pre->next;
	
	while (p!=NULL)
	{
		free(pre);
		
		// pre、p同步后移一个结点
		pre=p;
		p=pre->next;
	}
	
	// 此时p为NULL, pre指向尾结点, 释放它
	free(pre);
}

// 判线性表是否为空表
bool ListEmpty(ListNode *L)
{
	return(L->next==NULL);
}

// 求线性表的长度
int ListLength(ListNode *L)
{
	int i=0;
	
	// p指向头结点,n置为0(即头结点的序号为0)
	ListNode *p=L;
	
	while (p->next!=NULL)
	{
		i++;
		p=p->next;
	}
	
	// 循环结束,p指向尾结点,其序号i为结点个数
	return(i);
}

// 输出线性表
void DispList(ListNode *L)
{
	ListNode *p=L->next; // p指向首结点
	
	// p不为NULL,输出p结点的val域
	while (p!=NULL)
	{
		printf("%d ", p->val);
		
		// p移向下一个结点
		p=p->next;
	}
	printf("\n");
}

// 求线性表中第i个元素值
bool GetElem(ListNode *L,int i,int &e)
{
	int j=0;
	
	// i错误返回假
	if (i<=0) return false;
	
	// p指向头结点,j置为0(即头结点的序号为0)
	ListNode *p=L;
	
	// 找第i个结点p
	while (j<i && p!=NULL)
	{
		j++;
		p=p->next;
	}
	
	// 不存在第i个数据结点, 返回false
	if (p==NULL)
		return false;
	
	// 存在第i个数据结点,返回true
	else
	{
		e=p->val;
		return true;
	}
}

// 查找第一个值域为e的元素序号
int LocateElem(ListNode *L,int e)
{
	int i=1;
	
	// p指向首结点,i置为1(即首结点的序号为1)
	ListNode *p=L->next;	
	
	// 查找val值为e的结点, 其序号为i
	while (p!=NULL && p->val!=e)
	{
		p=p->next;
		i++;
	}
	
	// 不存在值为e的结点,返回0
	if (p==NULL)
		return(0);
	
	// 存在值为e的结点,返回其逻辑序号i
	else
		return(i);
}

// 插入第i个元素
bool ListInsert(ListNode *&L, int i, int e)
{
	int j=0;
	
	// i错误返回假
	if (i<=0) return false;
	
	// p指向头结点,j置为0(即头结点的序号为0)
	ListNode *p=L,*s;
	
	// 查找第i-1个结点p
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	
	// 未找到第i-1个结点,返回false
	if (p==NULL)
		return false;
	
	// 找到第i-1个结点p,插入新结点并返回true
	else
	{
		s=(ListNode *)malloc(sizeof(ListNode));
		
		// 创建新结点s, 其val域置为e
		s->val=e;
		
		// 将结点s插入到结点p之后
		s->next=p->next;
		p->next=s;
		return true;
	}
}

// 删除第i个元素
bool ListDelete(ListNode *&L,int i,int &e)
{
	int j=0;
	
	// i错误返回假
	if (i<=0) return false;
	
	// p指向头结点,j置为0(即头结点的序号为0)
	ListNode *p=L, *q;
	
	// 查找第i-1个结点
	while (j<i-1 && p!=NULL)
	{
		j++;
		p=p->next;
	}
	
	// 未找到第i-1个结点, 返回false
	if (p==NULL)
		return false;
	
	// 找到第i-1个结点p
	else
	{
		// q指向第i个结点
		q=p->next;
		
		// 若不存在第i个结点, 返回false
		if (q==NULL)
			return false;
		
		e=q->val;
		
		// 从单链表中删除q结点
		p->next=q->next;
		
		// 释放q结点
		free(q);	
		
		// 返回true表示成功删除第i个结点
		return true;
	}
}

// 遍历链表
void f(ListNode* h)
{
	if(h!=NULL)
	{
		printf("%d ",h->val);
		f(h->next);
	}
}

